package A1_哈希表;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LC_15三数之和 {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result=new ArrayList<>();
        for(int i=0;i<nums.length;i++){
            if(nums[i]>0) return result;
            if(i>0 && nums[i]==nums[i-1]) continue;
            int left=i+1;
            int right=nums.length-1;
            while(right>left){
                if(nums[i]+nums[left]+nums[right]>0)
                    right--;
                else if(nums[i]+nums[left]+nums[right]<0)
                    left++;
                else {
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                //此处用法
                    while(right>left && nums[right]==nums[right-1])
                        right--;
                    while(right>left && nums[left]==nums[left+1])
                        left++;
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}
